home *** CD-ROM | disk | FTP | other *** search
/ Programmer Plus 2007 / Programmer-Plus-2007.iso / Programming / Compilers / digital marsC compier / dm / stl / stl_vector.h < prev    next >
Encoding:
C/C++ Source or Header  |  2000-06-08  |  27.9 KB  |  870 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1996
  16.  * Silicon Graphics Computer Systems, Inc.
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Silicon Graphics makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  */
  26.  
  27. /* NOTE: This is an internal header file, included by other STL headers.
  28.  *   You should not attempt to use it directly.
  29.  */
  30.  
  31. #ifndef __SGI_STL_INTERNAL_VECTOR_H
  32. #define __SGI_STL_INTERNAL_VECTOR_H
  33.  
  34. #include <concept_checks.h>
  35.  
  36. __STL_BEGIN_NAMESPACE 
  37.  
  38. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  39. #pragma set woff 1174
  40. #pragma set woff 1375
  41. #endif
  42.  
  43. // The vector base class serves two purposes.  First, its constructor
  44. // and destructor allocate (but don't initialize) storage.  This makes
  45. // exception safety easier.  Second, the base class encapsulates all of
  46. // the differences between SGI-style allocators and standard-conforming
  47. // allocators.
  48.  
  49. #ifdef __STL_USE_STD_ALLOCATORS
  50.  
  51. // Base class for ordinary allocators.
  52. template <class _Tp, class _Allocator, bool _IsStatic>
  53. class _Vector_alloc_base {
  54. public:
  55.   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
  56.           allocator_type;
  57.   allocator_type get_allocator() const { return _M_data_allocator; }
  58.  
  59.   _Vector_alloc_base(const allocator_type& __a)
  60.     : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) 
  61.   {}
  62.   
  63. protected:
  64.   allocator_type _M_data_allocator;
  65.   _Tp* _M_start;
  66.   _Tp* _M_finish;
  67.   _Tp* _M_end_of_storage;
  68.  
  69.   _Tp* _M_allocate(size_t __n)
  70.     { return _M_data_allocator.allocate(__n); }
  71.   void _M_deallocate(_Tp* __p, size_t __n)
  72.     { if (__p) _M_data_allocator.deallocate(__p, __n); }
  73. };
  74.  
  75. // Specialization for allocators that have the property that we don't
  76. // actually have to store an allocator object.  
  77. template <class _Tp, class _Allocator>
  78. class _Vector_alloc_base<_Tp, _Allocator, true> {
  79. public:
  80.   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
  81.           allocator_type;
  82.   allocator_type get_allocator() const { return allocator_type(); }
  83.  
  84.   _Vector_alloc_base(const allocator_type&)
  85.     : _M_start(0), _M_finish(0), _M_end_of_storage(0) 
  86.   {}
  87.   
  88. protected:
  89.   _Tp* _M_start;
  90.   _Tp* _M_finish;
  91.   _Tp* _M_end_of_storage;
  92.  
  93.   typedef typename _Alloc_traits<_Tp, _Allocator>::_Alloc_type _Alloc_type;
  94.   _Tp* _M_allocate(size_t __n)
  95.     { return _Alloc_type::allocate(__n); }
  96.   void _M_deallocate(_Tp* __p, size_t __n)
  97.     { _Alloc_type::deallocate(__p, __n);}
  98. };
  99.  
  100. template <class _Tp, class _Alloc>
  101. struct _Vector_base
  102.   : public _Vector_alloc_base<_Tp, _Alloc,
  103.                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  104. {
  105.   typedef _Vector_alloc_base<_Tp, _Alloc, 
  106.                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  107.           _Base;
  108.   typedef typename _Base::allocator_type allocator_type;
  109.  
  110.   _Vector_base(const allocator_type& __a) : _Base(__a) {}
  111.   _Vector_base(size_t __n, const allocator_type& __a) : _Base(__a) {
  112.     _M_start = _M_allocate(__n);
  113.     _M_finish = _M_start;
  114.     _M_end_of_storage = _M_start + __n;
  115.   }
  116.  
  117.   ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
  118. };    
  119.  
  120. #else /* __STL_USE_STD_ALLOCATORS */
  121.  
  122. template <class _Tp, class _Alloc> 
  123. class _Vector_base {
  124. public:
  125.   typedef _Alloc allocator_type;
  126.   allocator_type get_allocator() const { return allocator_type(); }
  127.  
  128.   _Vector_base(const _Alloc&)
  129.     : _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
  130.   _Vector_base(size_t __n, const _Alloc&)
  131.     : _M_start(0), _M_finish(0), _M_end_of_storage(0) 
  132.   {
  133.     _M_start = _M_allocate(__n);
  134.     _M_finish = _M_start;
  135.     _M_end_of_storage = _M_start + __n;
  136.   }
  137.  
  138.   ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
  139.  
  140. protected:
  141.   _Tp* _M_start;
  142.   _Tp* _M_finish;
  143.   _Tp* _M_end_of_storage;
  144.  
  145.   typedef simple_alloc<_Tp, _Alloc> _M_data_allocator;
  146.   _Tp* _M_allocate(size_t __n)
  147.     { return _M_data_allocator::allocate(__n); }
  148.   void _M_deallocate(_Tp* __p, size_t __n) 
  149.     { _M_data_allocator::deallocate(__p, __n); }
  150. };
  151.  
  152. #endif /* __STL_USE_STD_ALLOCATORS */
  153.  
  154. template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
  155. class vector : protected _Vector_base<_Tp, _Alloc> 
  156. {
  157.   // requirements:
  158.  
  159.   __STL_CLASS_REQUIRES(_Tp, _Assignable);
  160.  
  161. private:
  162.   typedef _Vector_base<_Tp, _Alloc> _Base;
  163. public:
  164.   typedef _Tp value_type;
  165.   typedef value_type* pointer;
  166.   typedef const value_type* const_pointer;
  167.   typedef value_type* iterator;
  168.   typedef const value_type* const_iterator;
  169.   typedef value_type& reference;
  170.   typedef const value_type& const_reference;
  171.   typedef size_t size_type;
  172.   typedef ptrdiff_t difference_type;
  173.  
  174.   typedef typename _Base::allocator_type allocator_type;
  175.   allocator_type get_allocator() const { return _Base::get_allocator(); }
  176.  
  177. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  178.   typedef reverse_iterator<const_iterator> const_reverse_iterator;
  179.   typedef reverse_iterator<iterator> reverse_iterator;
  180. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  181.   typedef reverse_iterator<const_iterator, value_type, const_reference, 
  182.                            difference_type>  const_reverse_iterator;
  183.   typedef reverse_iterator<iterator, value_type, reference, difference_type>
  184.           reverse_iterator;
  185. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  186.  
  187. protected:
  188. #ifdef __STL_HAS_NAMESPACES
  189.   using _Base::_M_allocate;
  190.   using _Base::_M_deallocate;
  191.   using _Base::_M_start;
  192.   using _Base::_M_finish;
  193.   using _Base::_M_end_of_storage;
  194. #endif /* __STL_HAS_NAMESPACES */
  195.  
  196. protected:
  197.   void _M_insert_aux(iterator __position, const _Tp& __x);
  198.   void _M_insert_aux(iterator __position);
  199.  
  200. public:
  201.   iterator begin() { return _M_start; }
  202.   const_iterator begin() const { return _M_start; }
  203.   iterator end() { return _M_finish; }
  204.   const_iterator end() const { return _M_finish; }
  205.  
  206.   reverse_iterator rbegin()
  207.     { return reverse_iterator(end()); }
  208.   const_reverse_iterator rbegin() const
  209.     { return const_reverse_iterator(end()); }
  210.   reverse_iterator rend()
  211.     { return reverse_iterator(begin()); }
  212.   const_reverse_iterator rend() const
  213.     { return const_reverse_iterator(begin()); }
  214.  
  215.   size_type size() const
  216.     { return size_type(end() - begin()); }
  217.   size_type max_size() const
  218.     { return size_type(-1) / sizeof(_Tp); }
  219.   size_type capacity() const
  220.     { return size_type(_M_end_of_storage - begin()); }
  221.   bool empty() const
  222.     { return begin() == end(); }
  223.  
  224.   reference operator[](size_type __n) { return *(begin() + __n); }
  225.   const_reference operator[](size_type __n) const { return *(begin() + __n); }
  226.  
  227. #ifdef __STL_THROW_RANGE_ERRORS
  228.   void _M_range_check(size_type __n) const {
  229.     if (__n >= this->size())
  230.       __stl_throw_range_error("vector");
  231.   }
  232.  
  233.   reference at(size_type __n)
  234.     { _M_range_check(__n); return (*this)[__n]; }
  235.   const_reference at(size_type __n) const
  236.     { _M_range_check(__n); return (*this)[__n]; }
  237. #endif /* __STL_THROW_RANGE_ERRORS */
  238.  
  239.   explicit vector(const allocator_type& __a = allocator_type())
  240.     : _Base(__a) {}
  241.  
  242.   vector(size_type __n, const _Tp& __value,
  243.          const allocator_type& __a = allocator_type()) 
  244.     : _Base(__n, __a)
  245.     { _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
  246.  
  247.   explicit vector(size_type __n)
  248.     : _Base(__n, allocator_type())
  249.     { _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); }
  250.  
  251.   vector(const vector<_Tp, _Alloc>& __x) 
  252.     : _Base(__x.size(), __x.get_allocator())
  253.     { _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }
  254.  
  255. #ifdef __STL_MEMBER_TEMPLATES
  256.   // Check whether it's an integral type.  If so, it's not an iterator.
  257.   template <class _InputIterator>
  258.   vector(_InputIterator __first, _InputIterator __last,
  259.          const allocator_type& __a = allocator_type()) : _Base(__a) {
  260.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  261.     _M_initialize_aux(__first, __last, _Integral());
  262.   }
  263.  
  264.   template <class _Integer>
  265.   void _M_initialize_aux(_Integer __n, _Integer __value, __true_type) {
  266.     _M_start = _M_allocate(__n);
  267.     _M_end_of_storage = _M_start + __n; 
  268.     _M_finish = uninitialized_fill_n(_M_start, __n, __value);
  269.   }
  270.  
  271.   template <class _InputIterator>
  272.   void _M_initialize_aux(_InputIterator __first, _InputIterator __last,
  273.                          __false_type) {
  274.     _M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
  275.   }
  276.  
  277. #else
  278.   vector(const _Tp* __first, const _Tp* __last,
  279.          const allocator_type& __a = allocator_type())
  280.     : _Base(__last - __first, __a) 
  281.     { _M_finish = uninitialized_copy(__first, __last, _M_start); }
  282. #endif /* __STL_MEMBER_TEMPLATES */
  283.  
  284.   ~vector() { destroy(_M_start, _M_finish); }
  285.  
  286.   vector<_Tp, _Alloc>& operator=(const vector<_Tp, _Alloc>& __x);
  287.   void reserve(size_type __n) {
  288.     if (capacity() < __n) {
  289.       const size_type __old_size = size();
  290.       iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
  291.       destroy(_M_start, _M_finish);
  292.       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  293.       _M_start = __tmp;
  294.       _M_finish = __tmp + __old_size;
  295.       _M_end_of_storage = _M_start + __n;
  296.     }
  297.   }
  298.  
  299.   // assign(), a generalized assignment member function.  Two
  300.   // versions: one that takes a count, and one that takes a range.
  301.   // The range version is a member template, so we dispatch on whether
  302.   // or not the type is an integer.
  303.  
  304.   void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
  305.   void _M_fill_assign(size_type __n, const _Tp& __val);
  306.  
  307. #ifdef __STL_MEMBER_TEMPLATES
  308.   
  309.   template <class _InputIterator>
  310.   void assign(_InputIterator __first, _InputIterator __last) {
  311.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  312.     _M_assign_dispatch(__first, __last, _Integral());
  313.   }
  314.  
  315.   template <class _Integer>
  316.   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
  317.     { _M_fill_assign((size_type) __n, (_Tp) __val); }
  318.  
  319.   template <class _InputIter>
  320.   void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
  321.     { _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first)); }
  322.  
  323.   template <class _InputIterator>
  324.   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
  325.                      input_iterator_tag);
  326.  
  327.   template <class _ForwardIterator>
  328.   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
  329.                      forward_iterator_tag); 
  330.  
  331. #endif /* __STL_MEMBER_TEMPLATES */
  332.  
  333.   reference front() { return *begin(); }
  334.   const_reference front() const { return *begin(); }
  335.   reference back() { return *(end() - 1); }
  336.   const_reference back() const { return *(end() - 1); }
  337.  
  338.   void push_back(const _Tp& __x) {
  339.     if (_M_finish != _M_end_of_storage) {
  340.       construct(_M_finish, __x);
  341.       ++_M_finish;
  342.     }
  343.     else
  344.       _M_insert_aux(end(), __x);
  345.   }
  346.   void push_back() {
  347.     if (_M_finish != _M_end_of_storage) {
  348.       construct(_M_finish);
  349.       ++_M_finish;
  350.     }
  351.     else
  352.       _M_insert_aux(end());
  353.   }
  354.   void swap(vector<_Tp, _Alloc>& __x) {
  355.     __STD::swap(_M_start, __x._M_start);
  356.     __STD::swap(_M_finish, __x._M_finish);
  357.     __STD::swap(_M_end_of_storage, __x._M_end_of_storage);
  358.   }
  359.  
  360.   iterator insert(iterator __position, const _Tp& __x) {
  361.     size_type __n = __position - begin();
  362.     if (_M_finish != _M_end_of_storage && __position == end()) {
  363.       construct(_M_finish, __x);
  364.       ++_M_finish;
  365.     }
  366.     else
  367.       _M_insert_aux(__position, __x);
  368.     return begin() + __n;
  369.   }
  370.   iterator insert(iterator __position) {
  371.     size_type __n = __position - begin();
  372.     if (_M_finish != _M_end_of_storage && __position == end()) {
  373.       construct(_M_finish);
  374.       ++_M_finish;
  375.     }
  376.     else
  377.       _M_insert_aux(__position);
  378.     return begin() + __n;
  379.   }
  380. #ifdef __STL_MEMBER_TEMPLATES
  381.   // Check whether it's an integral type.  If so, it's not an iterator.
  382.   template <class _InputIterator>
  383.   void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
  384.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  385.     _M_insert_dispatch(__pos, __first, __last, _Integral());
  386.   }
  387.  
  388.   template <class _Integer>
  389.   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
  390.                           __true_type)
  391.     { _M_fill_insert(__pos, (size_type) __n, (_Tp) __val); }
  392.  
  393.   template <class _InputIterator>
  394.   void _M_insert_dispatch(iterator __pos,
  395.                           _InputIterator __first, _InputIterator __last,
  396.                           __false_type) {
  397.     _M_range_insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
  398.   }
  399. #else /* __STL_MEMBER_TEMPLATES */
  400.   void insert(iterator __position,
  401.               const_iterator __first, const_iterator __last);
  402. #endif /* __STL_MEMBER_TEMPLATES */
  403.  
  404.   void insert (iterator __pos, size_type __n, const _Tp& __x)
  405.     { _M_fill_insert(__pos, __n, __x); }
  406.  
  407.   void _M_fill_insert (iterator __pos, size_type __n, const _Tp& __x);
  408.  
  409.   void pop_back() {
  410.     --_M_finish;
  411.     destroy(_M_finish);
  412.   }
  413.   iterator erase(iterator __position) {
  414.     if (__position + 1 != end())
  415.       copy(__position + 1, _M_finish, __position);
  416.     --_M_finish;
  417.     destroy(_M_finish);
  418.     return __position;
  419.   }
  420.   iterator erase(iterator __first, iterator __last) {
  421.     iterator __i = copy(__last, _M_finish, __first);
  422.     destroy(__i, _M_finish);
  423.     _M_finish = _M_finish - (__last - __first);
  424.     return __first;
  425.   }
  426.  
  427.   void resize(size_type __new_size, const _Tp& __x) {
  428.     if (__new_size < size()) 
  429.       erase(begin() + __new_size, end());
  430.     else
  431.       insert(end(), __new_size - size(), __x);
  432.   }
  433.   void resize(size_type __new_size) { resize(__new_size, _Tp()); }
  434.   void clear() { erase(begin(), end()); }
  435.  
  436. protected:
  437.  
  438. #ifdef __STL_MEMBER_TEMPLATES
  439.   template <class _ForwardIterator>
  440.   iterator _M_allocate_and_copy(size_type __n, _ForwardIterator __first, 
  441.                                                _ForwardIterator __last)
  442. {
  443.     iterator __result = _M_allocate(__n);
  444.     __STL_TRY {
  445.       uninitialized_copy(__first, __last, __result);
  446.       return __result;
  447.     }
  448.     __STL_UNWIND(_M_deallocate(__result, __n));
  449.   }
  450. #else /* __STL_MEMBER_TEMPLATES */
  451.   iterator _M_allocate_and_copy(size_type __n, const_iterator __first, 
  452.                                                const_iterator __last)
  453.   {
  454.     iterator __result = _M_allocate(__n);
  455.     __STL_TRY {
  456.       uninitialized_copy(__first, __last, __result);
  457.       return __result;
  458.     }
  459.     __STL_UNWIND(_M_deallocate(__result, __n));
  460.   }
  461. #endif /* __STL_MEMBER_TEMPLATES */
  462.  
  463.  
  464. #ifdef __STL_MEMBER_TEMPLATES
  465.   template <class _InputIterator>
  466.   void _M_range_initialize(_InputIterator __first,  
  467.                            _InputIterator __last, input_iterator_tag)
  468.   {
  469.     for ( ; __first != __last; ++__first)
  470.       push_back(*__first);
  471.   }
  472.  
  473.   // This function is only called by the constructor. 
  474.   template <class _ForwardIterator>
  475.   void _M_range_initialize(_ForwardIterator __first,
  476.                            _ForwardIterator __last, forward_iterator_tag)
  477.   {
  478.     size_type __n = 0;
  479.     distance(__first, __last, __n);
  480.     _M_start = _M_allocate(__n);
  481.     _M_end_of_storage = _M_start + __n;
  482.     _M_finish = uninitialized_copy(__first, __last, _M_start);
  483.   }
  484.  
  485.   template <class _InputIterator>
  486.   void _M_range_insert(iterator __pos,
  487.                        _InputIterator __first, _InputIterator __last,
  488.                        input_iterator_tag);
  489.  
  490.   template <class _ForwardIterator>
  491.   void _M_range_insert(iterator __pos,
  492.                        _ForwardIterator __first, _ForwardIterator __last,
  493.                        forward_iterator_tag);
  494.  
  495. #endif /* __STL_MEMBER_TEMPLATES */
  496. };
  497.  
  498. template <class _Tp, class _Alloc>
  499. inline bool 
  500. operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
  501. {
  502.   return __x.size() == __y.size() &&
  503.          equal(__x.begin(), __x.end(), __y.begin());
  504. }
  505.  
  506. template <class _Tp, class _Alloc>
  507. inline bool 
  508. operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
  509. {
  510.   return lexicographical_compare(__x.begin(), __x.end(), 
  511.                                  __y.begin(), __y.end());
  512. }
  513.  
  514. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  515.  
  516. template <class _Tp, class _Alloc>
  517. inline void swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
  518. {
  519.   __x.swap(__y);
  520. }
  521.  
  522. template <class _Tp, class _Alloc>
  523. inline bool
  524. operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
  525.   return !(__x == __y);
  526. }
  527.  
  528. template <class _Tp, class _Alloc>
  529. inline bool
  530. operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
  531.   return __y < __x;
  532. }
  533.  
  534. template <class _Tp, class _Alloc>
  535. inline bool
  536. operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
  537.   return !(__y < __x);
  538. }
  539.  
  540. template <class _Tp, class _Alloc>
  541. inline bool
  542. operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
  543.   return !(__x < __y);
  544. }
  545.  
  546. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  547.  
  548. template <class _Tp, class _Alloc>
  549. vector<_Tp,_Alloc>& 
  550. vector<_Tp,_Alloc>::operator=(const vector<_Tp, _Alloc>& __x)
  551. {
  552.   if (&__x != this) {
  553.     const size_type __xlen = __x.size();
  554.     if (__xlen > capacity()) {
  555.       iterator __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
  556.       destroy(_M_start, _M_finish);
  557.       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  558.       _M_start = __tmp;
  559.       _M_end_of_storage = _M_start + __xlen;
  560.     }
  561.     else if (size() >= __xlen) {
  562.       iterator __i = copy(__x.begin(), __x.end(), begin());
  563.       destroy(__i, _M_finish);
  564.     }
  565.     else {
  566.       copy(__x.begin(), __x.begin() + size(), _M_start);
  567.       uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
  568.     }
  569.     _M_finish = _M_start + __xlen;
  570.   }
  571.   return *this;
  572. }
  573.  
  574. template <class _Tp, class _Alloc>
  575. void vector<_Tp, _Alloc>::_M_fill_assign(size_t __n, const value_type& __val) 
  576. {
  577.   if (__n > capacity()) {
  578.     vector<_Tp, _Alloc> __tmp(__n, __val, get_allocator());
  579.     __tmp.swap(*this);
  580.   }
  581.   else if (__n > size()) {
  582.     fill(begin(), end(), __val);
  583.     _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val);
  584.   }
  585.   else
  586.     erase(fill_n(begin(), __n, __val), end());
  587. }
  588.  
  589. #ifdef __STL_MEMBER_TEMPLATES
  590.  
  591. template <class _Tp, class _Alloc> template <class _InputIter>
  592. void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last,
  593.                                         input_iterator_tag) {
  594.   iterator __cur = begin();
  595.   for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
  596.     *__cur = *__first;
  597.   if (__first == __last)
  598.     erase(__cur, end());
  599.   else
  600.     insert(end(), __first, __last);
  601. }
  602.  
  603. template <class _Tp, class _Alloc> template <class _ForwardIter>
  604. void
  605. vector<_Tp, _Alloc>::_M_assign_aux(_ForwardIter __first, _ForwardIter __last,
  606.                                    forward_iterator_tag) {
  607.   size_type __len = 0;
  608.   distance(__first, __last, __len);
  609.  
  610.   if (__len > capacity()) {
  611.     iterator __tmp = _M_allocate_and_copy(__len, __first, __last);
  612.     destroy(_M_start, _M_finish);
  613.     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  614.     _M_start = __tmp;
  615.     _M_end_of_storage = _M_finish = _M_start + __len;
  616.   }
  617.   else if (size() >= __len) {
  618.     iterator __new_finish = copy(__first, __last, _M_start);
  619.     destroy(__new_finish, _M_finish);
  620.     _M_finish = __new_finish;
  621.   }
  622.   else {
  623.     _ForwardIter __mid = __first;
  624.     advance(__mid, size());
  625.     copy(__first, __mid, _M_start);
  626.     _M_finish = uninitialized_copy(__mid, __last, _M_finish);
  627.   }
  628. }
  629.  
  630. #endif /* __STL_MEMBER_TEMPLATES */
  631.  
  632. template <class _Tp, class _Alloc>
  633. void 
  634. vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
  635. {
  636.   if (_M_finish != _M_end_of_storage) {
  637.     construct(_M_finish, *(_M_finish - 1));
  638.     ++_M_finish;
  639.     _Tp __x_copy = __x;
  640.     copy_backward(__position, _M_finish - 2, _M_finish - 1);
  641.     *__position = __x_copy;
  642.   }
  643.   else {
  644.     const size_type __old_size = size();
  645.     const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
  646.     iterator __new_start = _M_allocate(__len);
  647.     iterator __new_finish = __new_start;
  648.     __STL_TRY {
  649.       __new_finish = uninitialized_copy(_M_start, __position, __new_start);
  650.       construct(__new_finish, __x);
  651.       ++__new_finish;
  652.       __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
  653.     }
  654.     __STL_UNWIND((destroy(__new_start,__new_finish), 
  655.                   _M_deallocate(__new_start,__len)));
  656.     destroy(begin(), end());
  657.     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  658.     _M_start = __new_start;
  659.     _M_finish = __new_finish;
  660.     _M_end_of_storage = __new_start + __len;
  661.   }
  662. }
  663.  
  664. template <class _Tp, class _Alloc>
  665. void 
  666. vector<_Tp, _Alloc>::_M_insert_aux(iterator __position)
  667. {
  668.   if (_M_finish != _M_end_of_storage) {
  669.     construct(_M_finish, *(_M_finish - 1));
  670.     ++_M_finish;
  671.     copy_backward(__position, _M_finish - 2, _M_finish - 1);
  672.     *__position = _Tp();
  673.   }
  674.   else {
  675.     const size_type __old_size = size();
  676.     const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
  677.     iterator __new_start = _M_allocate(__len);
  678.     iterator __new_finish = __new_start;
  679.     __STL_TRY {
  680.       __new_finish = uninitialized_copy(_M_start, __position, __new_start);
  681.       construct(__new_finish);
  682.       ++__new_finish;
  683.       __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
  684.     }
  685.     __STL_UNWIND((destroy(__new_start,__new_finish), 
  686.                   _M_deallocate(__new_start,__len)));
  687.     destroy(begin(), end());
  688.     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  689.     _M_start = __new_start;
  690.     _M_finish = __new_finish;
  691.     _M_end_of_storage = __new_start + __len;
  692.   }
  693. }
  694.  
  695. template <class _Tp, class _Alloc>
  696. void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n, 
  697.                                          const _Tp& __x)
  698. {
  699.   if (__n != 0) {
  700.     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
  701.       _Tp __x_copy = __x;
  702.       const size_type __elems_after = _M_finish - __position;
  703.       iterator __old_finish = _M_finish;
  704.       if (__elems_after > __n) {
  705.         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
  706.         _M_finish += __n;
  707.         copy_backward(__position, __old_finish - __n, __old_finish);
  708.         fill(__position, __position + __n, __x_copy);
  709.       }
  710.       else {
  711.         uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
  712.         _M_finish += __n - __elems_after;
  713.         uninitialized_copy(__position, __old_finish, _M_finish);
  714.         _M_finish += __elems_after;
  715.         fill(__position, __old_finish, __x_copy);
  716.       }
  717.     }
  718.     else {
  719.       const size_type __old_size = size();        
  720.       const size_type __len = __old_size + max(__old_size, __n);
  721.       iterator __new_start = _M_allocate(__len);
  722.       iterator __new_finish = __new_start;
  723.       __STL_TRY {
  724.         __new_finish = uninitialized_copy(_M_start, __position, __new_start);
  725.         __new_finish = uninitialized_fill_n(__new_finish, __n, __x);
  726.         __new_finish
  727.           = uninitialized_copy(__position, _M_finish, __new_finish);
  728.       }
  729.       __STL_UNWIND((destroy(__new_start,__new_finish), 
  730.                     _M_deallocate(__new_start,__len)));
  731.       destroy(_M_start, _M_finish);
  732.       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  733.       _M_start = __new_start;
  734.       _M_finish = __new_finish;
  735.       _M_end_of_storage = __new_start + __len;
  736.     }
  737.   }
  738. }
  739.  
  740. #ifdef __STL_MEMBER_TEMPLATES
  741.  
  742. template <class _Tp, class _Alloc> template <class _InputIterator>
  743. void 
  744. vector<_Tp, _Alloc>::_M_range_insert(iterator __pos, 
  745.                                      _InputIterator __first, 
  746.                                      _InputIterator __last,
  747.                                      input_iterator_tag)
  748. {
  749.   for ( ; __first != __last; ++__first) {
  750.     __pos = insert(__pos, *__first);
  751.     ++__pos;
  752.   }
  753. }
  754.  
  755. template <class _Tp, class _Alloc> template <class _ForwardIterator>
  756. void 
  757. vector<_Tp, _Alloc>::_M_range_insert(iterator __position,
  758.                                      _ForwardIterator __first,
  759.                                      _ForwardIterator __last,
  760.                                      forward_iterator_tag)
  761. {
  762.   if (__first != __last) {
  763.     size_type __n = 0;
  764.     distance(__first, __last, __n);
  765.     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
  766.       const size_type __elems_after = _M_finish - __position;
  767.       iterator __old_finish = _M_finish;
  768.       if (__elems_after > __n) {
  769.         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
  770.         _M_finish += __n;
  771.         copy_backward(__position, __old_finish - __n, __old_finish);
  772.         copy(__first, __last, __position);
  773.       }
  774.       else {
  775.         _ForwardIterator __mid = __first;
  776.         advance(__mid, __elems_after);
  777.         uninitialized_copy(__mid, __last, _M_finish);
  778.         _M_finish += __n - __elems_after;
  779.         uninitialized_copy(__position, __old_finish, _M_finish);
  780.         _M_finish += __elems_after;
  781.         copy(__first, __mid, __position);
  782.       }
  783.     }
  784.     else {
  785.       const size_type __old_size = size();
  786.       const size_type __len = __old_size + max(__old_size, __n);
  787.       iterator __new_start = _M_allocate(__len);
  788.       iterator __new_finish = __new_start;
  789.       __STL_TRY {
  790.         __new_finish = uninitialized_copy(_M_start, __position, __new_start);
  791.         __new_finish = uninitialized_copy(__first, __last, __new_finish);
  792.         __new_finish
  793.           = uninitialized_copy(__position, _M_finish, __new_finish);
  794.       }
  795.       __STL_UNWIND((destroy(__new_start,__new_finish), 
  796.                     _M_deallocate(__new_start,__len)));
  797.       destroy(_M_start, _M_finish);
  798.       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  799.       _M_start = __new_start;
  800.       _M_finish = __new_finish;
  801.       _M_end_of_storage = __new_start + __len;
  802.     }
  803.   }
  804. }
  805.  
  806. #else /* __STL_MEMBER_TEMPLATES */
  807.  
  808. template <class _Tp, class _Alloc>
  809. void 
  810. vector<_Tp, _Alloc>::insert(iterator __position, 
  811.                             const_iterator __first, 
  812.                             const_iterator __last)
  813. {
  814.   if (__first != __last) {
  815.     size_type __n = 0;
  816.     distance(__first, __last, __n);
  817.     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
  818.       const size_type __elems_after = _M_finish - __position;
  819.       iterator __old_finish = _M_finish;
  820.       if (__elems_after > __n) {
  821.         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
  822.         _M_finish += __n;
  823.         copy_backward(__position, __old_finish - __n, __old_finish);
  824.         copy(__first, __last, __position);
  825.       }
  826.       else {
  827.         uninitialized_copy(__first + __elems_after, __last, _M_finish);
  828.         _M_finish += __n - __elems_after;
  829.         uninitialized_copy(__position, __old_finish, _M_finish);
  830.         _M_finish += __elems_after;
  831.         copy(__first, __first + __elems_after, __position);
  832.       }
  833.     }
  834.     else {
  835.       const size_type __old_size = size();
  836.       const size_type __len = __old_size + max(__old_size, __n);
  837.       iterator __new_start = _M_allocate(__len);
  838.       iterator __new_finish = __new_start;
  839.       __STL_TRY {
  840.         __new_finish = uninitialized_copy(_M_start, __position, __new_start);
  841.         __new_finish = uninitialized_copy(__first, __last, __new_finish);
  842.         __new_finish
  843.           = uninitialized_copy(__position, _M_finish, __new_finish);
  844.       }
  845.       __STL_UNWIND((destroy(__new_start,__new_finish),
  846.                     _M_deallocate(__new_start,__len)));
  847.       destroy(_M_start, _M_finish);
  848.       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  849.       _M_start = __new_start;
  850.       _M_finish = __new_finish;
  851.       _M_end_of_storage = __new_start + __len;
  852.     }
  853.   }
  854. }
  855.  
  856. #endif /* __STL_MEMBER_TEMPLATES */
  857.  
  858. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  859. #pragma reset woff 1174
  860. #pragma reset woff 1375
  861. #endif
  862.  
  863. __STL_END_NAMESPACE 
  864.  
  865. #endif /* __SGI_STL_INTERNAL_VECTOR_H */
  866.  
  867. // Local Variables:
  868. // mode:C++
  869. // End:
  870.